#define DEBUG
#include <cstdio>

using namespace std;

const int mods=998244353;

long long qpower(long long a, int n, int mods) {
  long long s=1;
  for (; n>1; n/=2) {
    if (n%2) {
      s = s*a%mods;
    }
    a = a*a%mods;
  }
  return a*s%mods;
}

int main() {
  freopen("division.in", "r", stdin);
  freopen("division.out", "w", stdout);

  int id, t;
  scanf("%d %d", &id, &t);
  for (int ti=1; ti<=t; ti++) {
    int c, m;
    long long n=1;
    scanf("%d %d", &c, &m);
    for (int i=1; i<=c; i++) {
      int x;
      scanf("%d", &x);
      n *= x;
    }

    long long ans=0;
    for (long long i=1; i<=n; i++) {
      if (qpower(i, m, n)==i%n) {
	ans = (ans+1)%mods;
      }
    }
    printf("%lld\n", ans);
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
